#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const int N=5e5+5;
int n,m,q,a[N],b[N],Q[N];
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	freopen("clear.in","r",stdin);
	freopen("clear.out","w",stdout);
	cin>>n>>m>>q;
	for(int i=1;i<=n;++i)cin>>a[i];
	for(int i=1;i<=q;++i){
		int l,r;cin>>l>>r;LL ans=0;
		copy(a+l,a+r+1,b+1);
		int k=r-l+1,q=0;b[k+1]=0;
		for(int j=k+1;j>=1;--j)if((b[j]-=b[j-1])<0)Q[++q]=j;
		for(int j=1;j<=k;++j)for(ans+=b[j];b[j]>0;)
			if(Q[q]<=j+m)if(b[Q[q]]+b[j]>=0)b[j]+=b[Q[q]],b[Q[q--]]=0;else b[Q[q]]+=b[j],b[j]=0;
			else b[j+m]+=b[j],b[j]=0;
		cout<<ans<<'\n';
	}
	return 0;
}
/*
  .
 .*
.**
*/